package com.mccken.practice.top100.Top_1$20.Top_24;

import com.mccken.practice.top100.ListNode;

/**
 * @program: mccken-collect
 * @description:
 * @author: mccken
 * @create: 2024-02-14 18:56
 **/
public class DetectCycle {

	public ListNode detectCycle(ListNode head) {
		if (head == null) {
			return null;
		}
		ListNode slow = head;
		ListNode fast = head;

		boolean hasCycle = false;
		while (fast.next != null && fast.next.next != null) {
			slow = slow.next;
			fast = fast.next.next;

			if (slow == fast) {
				hasCycle = true;
				break;
			}
		}

		if (hasCycle) {
			slow = head;
			while (slow != fast) {
				slow = slow.next;
				fast = fast.next;
			}
			
			return slow;
		}
		return null;
	}
}
